package 数据结构.双向链表;

//双向链表
public class DoublyLinkedList<T> {

    private Node frist;
    private Node last;

    class Node<T>{
        T data;
        Node next;
        Node pre;

        public Node(T data){
            this.data = data;
        }

        public void displayCurrentNode() {
            System.out.print(data + "  ");
        }
    }

    public DoublyLinkedList(){
        frist = null;
        last = null;
    }

    public boolean isEmpty(){
        return frist == null;
    }

    //添加到首部
    public void addFrist(T dataue){
        Node<T> newNode= new Node(dataue);
        if(isEmpty()){ // 如果链表为空
            last = newNode; //last -> newNode
        }else {
            frist.pre = newNode; // frist.pre -> newNode
        }
        newNode.next = frist; // newNode -> frist
        frist = newNode; // frist -> newNode
    }

    public void addLast(T dataue){
        Node<T> newNode= new Node(dataue);
        if(isEmpty()){ // 如果链表为空
            frist = newNode; // 表头指针直接指向新节点
        }else {
            last.next = newNode; //last指向的节点指向新节点
            newNode.pre = last; //新节点的前驱指向last指针
        }
        last = newNode; // last指向新节点
    }

    public boolean addBefore(T key,T dataue){

        Node<T> cur = frist;
        if(frist.next.data == key){
            addFrist(dataue);
            return true;
        }else {
            while (cur.next.data != key) {
                cur = cur.next;
                if(cur == null){
                    return false;
                }
            }
            Node<T> newNode= new Node(dataue);
            newNode.next = cur.next;
            cur.next.pre = newNode;
            newNode.pre = cur;
            cur.next = newNode;
            return true;
        }
    }

    public void addAfter(T key,T dataue)throws RuntimeException{
        Node<T> cur = frist;
        while(cur.data!=key){ //经过循环，cur指针指向指定节点
            cur = cur.next;
            if(cur == null){ // 找不到该节点
                throw new RuntimeException("Node is not exists");
            }
        }
        Node<T> newNode = new Node(dataue);
        if (cur == last){ // 如果当前结点是尾节点
            newNode.next = null; // 新节点指向null
            last =newNode; // last指针指向新节点
        }else {
            newNode.next = cur.next; //新节点next指针，指向当前结点的next
            cur.next.pre = newNode; //当前结点的前驱指向新节点
        }
        newNode.pre = cur;//当前结点的前驱指向当前结点
        cur.next = newNode; //当前结点的后继指向新节点
    }

    public void deleteFrist(){
        if(frist.next == null){
            last = null;
        }else {
            frist.next.pre = null;
        }
        frist = frist.next;
    }

    public void deleteLast(){
        if(frist.next == null){
            frist = null;
        }else {
            last.pre.next = null;
        }
        last = last.pre;
    }

    public void deleteKey(T key)throws RuntimeException{
        Node<T> cur = frist;
        while(cur.data!= key){
            cur = cur.next;
            if(cur == null){ //不存在该节点
                throw new RuntimeException("Node is not exists");
            }
        }
        if(cur == frist){ // 如果frist指向的节点
            frist = cur.next; //frist指针后移
        }else {
            cur.pre.next = cur.next;//前面节点的后继指向当前节点的后一个节点
        }
        if(cur == last){ // 如果当前节点是尾节点
            last = cur.pre; // 尾节点的前驱前移
        }else {
            cur.next.pre = cur.pre; //后面节点的前驱指向当前节点的前一个节点
        }
    }

    public T queryPre(T dataue)throws RuntimeException{
        Node<T> cur = frist;
        if(frist.data == dataue){
            throw new RuntimeException("Not find "+dataue+"pre");
        }
        while(cur.next.data!=dataue){
            cur = cur.next;
            if(cur.next == null){
                throw new RuntimeException(dataue +"pre is not exeist!");
            }
        }

        return cur.data;
    }

    public void displayForward(){
        Node<T> cur = frist;
        while(cur!=null){
            cur.displayCurrentNode();
            cur = cur.next;
        }
        System.out.println();

    }
    public void displayBackward(){
        Node<T> cur = last;
        while(cur!=null){
            cur.displayCurrentNode();
            cur = cur.pre;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        DoublyLinkedList<String> linkedList = new DoublyLinkedList<>();
        linkedList.addFrist("1");
        linkedList.addFrist("2");
        linkedList.addFrist("3");
        linkedList.addLast("3");
        linkedList.addLast("2");
        linkedList.addLast("1");
        linkedList.displayBackward();
    }


}

/*作者：爱西考的王同学
链接：https://juejin.cn/post/6844904050077466637
来源：掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/
